﻿#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <queue>
#include <unordered_map>
#include "BinaryTreeNode.h"

using namespace std;

#define MAX(a, b) (a > b ? a : b)

/** 二叉树遍历
 * 先序遍历 head -> left -> right<br></br>
 * 中序遍历 left -> head -> right<br></br>
 * 后续遍历 left -> right -> head<br></br>
 *            1
 *          /  \
 *         2    3
 *        / \  / \
 *       4   5 6  7
 * <br></br>
 * 完整遍历: 1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,3,7,7,7,3,1<br></br>
 * 先序遍历(取每个节点的第一次出现): 1,2,4,5,3,6,7<br></br>
 * 中序遍历(取每个节点的第二次出现): 4,2,5,1,6,3,7<br></br>
 * 后续遍历(取每个节点的第三次出现): 4,5,2,6,7,3,1
 */

// 递归遍历基础函数
static void normalRecur(BinaryTreeNode* head)
{
	if (!head) return;

	normalRecur(head->left);
	normalRecur(head->right);
}

// 递归删除节点
static void deleteRecur(BinaryTreeNode* head)
{
	if (!head) return;

	deleteRecur(head->left);
	deleteRecur(head->right);
	delete(head);
}

// 递归先序遍历
static void normalPreOrderRecur(BinaryTreeNode* head)
{
	if (!head) return;

	printf("%d->", head->value);
	normalPreOrderRecur(head->left);
	normalPreOrderRecur(head->right);
}

// 递归中序遍历
static void normalInOrderRecur(BinaryTreeNode* head)
{
	if (!head) return;

	normalInOrderRecur(head->left);
	printf("%d->", head->value);
	normalInOrderRecur(head->right);
}

// 递归后续遍历
static void normalPostOrderRecur(BinaryTreeNode* head)
{
	if (!head) return;

	normalPostOrderRecur(head->left);
	normalPostOrderRecur(head->right);
	printf("%d->", head->value);
}

// 非递归先序遍历
static void preOrder(BinaryTreeNode* head)
{
	stack<BinaryTreeNode*> nodeStack;
	nodeStack.push(head);
	BinaryTreeNode* cur = nullptr;
	while (!nodeStack.empty())
	{
		cur = nodeStack.top();
		printf("%d->", cur->value);
		nodeStack.pop();
		if (cur->right)
		{
			nodeStack.push(cur->right);
		}

		if (cur->left)
		{
			nodeStack.push(cur->left);
		}
	}
}

// 非递归中序遍历
static void inOrder(BinaryTreeNode* head)
{
	stack<BinaryTreeNode*> nodeStack;
	while (!nodeStack.empty() || head)
	{
		if (head)
		{
			nodeStack.push(head);
			head = head->left;
		}
		else
		{
			head = nodeStack.top();
			printf("%d->", head->value);
			nodeStack.pop();
			head = head->right;
		}
	}
}

// 非递归后续遍历
static void postOrder(BinaryTreeNode* head)
{
	stack<BinaryTreeNode*> stack1;
	stack<BinaryTreeNode*> stack2;
	stack1.push(head);
	while (!stack1.empty())
	{
		head = stack1.top();
		stack1.pop();
		stack2.push(head);
		if (head->left)
		{
			stack1.push(head->left);
		}

		if (head->right)
		{
			stack1.push(head->right);
		}
	}

	while (!stack2.empty())
	{
		head = stack2.top();
		printf("%d->", head->value);
		stack2.pop();
	}
}

// Morris 遍历
static void morris(BinaryTreeNode* head)
{
	BinaryTreeNode* cur = head;
	BinaryTreeNode* mostRight = nullptr;
	while (cur)
	{
		if (!cur->left)
		{
			cur = cur->right;
		}
		else
		{
			mostRight = cur->left;
			while (mostRight->right && mostRight->right != cur)
			{
				mostRight = mostRight->right;
			}

			if (!mostRight->right)
			{
				mostRight->right = cur;
				cur = cur->left;
			}
			else
			{
				mostRight->right = nullptr;
				cur = cur->right;
			}
		}
	}
}

// Morris 先序遍历
static void morrisPreOrder(BinaryTreeNode* head)
{
	BinaryTreeNode* cur = head;
	BinaryTreeNode* mostRight = nullptr;
	while (cur)
	{
		if (!cur->left)
		{
			printf("%d->", cur->value);
			cur = cur->right;
		}
		else
		{
			mostRight = cur->left;
			while (mostRight->right && mostRight->right != cur)
			{
				mostRight = mostRight->right;
			}

			if (!mostRight->right)
			{
				mostRight->right = cur;
				printf("%d->", cur->value);
				cur = cur->left;
			}
			else
			{
				mostRight->right = nullptr;
				cur = cur->right;
			}
		}
	}
}

// Morris 中序遍历
static void morrisInOrder(BinaryTreeNode* head)
{
	BinaryTreeNode* cur = head;
	BinaryTreeNode* mostRight = nullptr;
	while (cur)
	{
		if (!cur->left)
		{
			printf("%d->", cur->value);
			cur = cur->right;
		}
		else
		{
			mostRight = cur->left;
			while (mostRight->right && mostRight->right != cur)
			{
				mostRight = mostRight->right;
			}

			if (!mostRight->right)
			{
				mostRight->right = cur;
				cur = cur->left;
			}
			else
			{
				mostRight->right = nullptr;
				printf("%d->", cur->value);
				cur = cur->right;
			}
		}
	}
}

// 反转右子树构成的链表，返回新的根节点
static BinaryTreeNode* reverseRight(BinaryTreeNode* right)
{
	if (!right) return nullptr;
	if (!right->right) return right;

	BinaryTreeNode* nextNode = nullptr;
	BinaryTreeNode* preNode = nullptr;
	BinaryTreeNode* reverseHead = nullptr;
	while (true)
	{
		nextNode = right->right;
		right->right = preNode;
		preNode = right;
		right = nextNode;

		if (nextNode)
		{
			reverseHead = nextNode;
		}
		else
		{
			break;
		}
	}

	return reverseHead;
}

// Morris 后续遍历
static void morrisPostOrder(BinaryTreeNode* head)
{
	BinaryTreeNode* cur = head;
	BinaryTreeNode* mostRight = nullptr;
	BinaryTreeNode* reversed = nullptr;
	BinaryTreeNode* curForPrint = nullptr;
	while (cur)
	{
		if (!cur->left)
		{
			cur = cur->right;
		}
		else
		{
			mostRight = cur->left;
			while (mostRight->right && mostRight->right != cur)
			{
				mostRight = mostRight->right;
			}

			if (!mostRight->right)
			{
				mostRight->right = cur;
				cur = cur->left;
			}
			else
			{
				mostRight->right = nullptr;

				reversed = reverseRight(cur->left);
				curForPrint = reversed;
				while (curForPrint)
				{
					printf("%d->", curForPrint->value);
					curForPrint = curForPrint->right;
				}

				reverseRight(reversed);

				cur = cur->right;
			}
		}
	}

	// 打印整颗树的右边界
	reversed = reverseRight(head);
	curForPrint = reversed;
	while (curForPrint)
	{
		printf("%d->", curForPrint->value);
		curForPrint = curForPrint->right;
	}

	reverseRight(reversed);
}

// 宽度优先遍历 使用队列
static void breadthFirstSearch_byQueue(BinaryTreeNode* head)
{
	queue<BinaryTreeNode*> queue;
	queue.push(head);
	while (!queue.empty())
	{
		head = queue.front();
		printf("%d->", head->value);
		queue.pop();
		if (head->left)
		{
			queue.push(head->left);
		}

		if (head->right)
		{
			queue.push(head->right);
		}
	}
}

// 宽度优先遍历 使用队列，并记录每个节点所在的层级
static int breadthFirstSearch_byQueue_noteLayerForEveryNode(BinaryTreeNode* head)
{
	queue<BinaryTreeNode*> queue;
	queue.push(head);
	int currentLayer = 1;
	int maxWidth = 0;
	int currentWidth = 0;
	unordered_map<BinaryTreeNode*, int> layerMap;
	layerMap.insert({ head, currentLayer });
	while (!queue.empty())
	{
		head = queue.front();
		queue.pop();
		printf("%d->", head->value);
		auto headData = layerMap.find(head);
		if (headData != layerMap.end() && headData->second == currentLayer)
		{
			++currentWidth;
		}
		else
		{
			maxWidth = MAX(currentWidth, maxWidth);
			currentWidth = 1;
			++currentLayer;
		}

		if (head->left)
		{
			queue.push(head->left);
			layerMap.insert({ head->left, currentLayer + 1 });
		}

		if (head->right)
		{
			queue.push(head->right);
			layerMap.insert({ head->right, currentLayer + 1 });
		}
	}

	maxWidth = MAX(currentWidth, maxWidth);

	printf("\n");
	printf("maxWidth=%d, maxLayer=%d", maxWidth, currentLayer);
	return maxWidth;
}

// 宽度优先遍历 使用队列，并不通过哈希表计算出最大宽度
static int breadthFirstSearch_byQueue_calcMaxWidthWithoutHashMap(BinaryTreeNode* head)
{
	queue<BinaryTreeNode*> queue;
	queue.push(head);
	int currentLayer = 0;
	int currentWidth = 0;
	int maxWidth = 0;
	BinaryTreeNode* currentLayerEnd = head;
	BinaryTreeNode* nextLayerEnd = nullptr;
	while (!queue.empty())
	{
		head = queue.front();
		printf("%d->", head->value);
		queue.pop();
		if (head->left)
		{
			queue.push(head->left);
			nextLayerEnd = head->left;
		}

		if (head->right)
		{
			queue.push(head->right);
			nextLayerEnd = head->right;
		}

		if (head == currentLayerEnd)
		{
			currentLayerEnd = nextLayerEnd;
			nextLayerEnd = nullptr;
			maxWidth = MAX(currentWidth, maxWidth);
			currentWidth = 1;
			++currentLayer;
		}
		else
		{
			++currentWidth;
		}
	}

	printf("\n");
	printf("maxWidth=%d, maxLayer=%d", maxWidth, currentLayer);
	return maxWidth;
}

// 获取head下所有子节点的个数，包括自己
static int getNodeCount(BinaryTreeNode* head)
{
	if (!head) return 0;

	int leftCount = getNodeCount(head->left);
	int rightCount = getNodeCount(head->right);
	return leftCount + rightCount + 1;
}

// 获取head为根节点的子树的深度
static int getDepth(BinaryTreeNode* head)
{
	if (!head) return 0;

	int leftDepth = getDepth(head->left);
	int rightDepth = getDepth(head->right);
	return MAX(leftDepth, rightDepth) + 1;
}

int main_OrderRecur()
{
	auto head = new BinaryTreeNode(1);
	head->left = new BinaryTreeNode(2);
	head->right = new BinaryTreeNode(3);
	head->left->left = new BinaryTreeNode(4);
	head->left->right = new BinaryTreeNode(5);
	head->right->left = new BinaryTreeNode(6);
	head->right->right = new BinaryTreeNode(7);
	head->left->left->left = new BinaryTreeNode(8);
	head->left->left->right = new BinaryTreeNode(9);
	head->left->right->left = new BinaryTreeNode(10);
	head->left->right->right = new BinaryTreeNode(11);
	head->right->left->left = new BinaryTreeNode(12);
	head->right->left->right = new BinaryTreeNode(13);
	head->right->right->left = new BinaryTreeNode(14);
	head->right->right->right = new BinaryTreeNode(15);
	head->left->left->left->left = new BinaryTreeNode(16);

	breadthFirstSearch_byQueue_calcMaxWidthWithoutHashMap(head);

	printf("\n");

	int nodeCount = getNodeCount(head);
	printf("node count=%d\n", nodeCount);
	int depth = getDepth(head);
	printf("depth=%d\n", depth);

	deleteRecur(head);

	return 0;
}